package c;



/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-05-05
 * Time: 10:21
 */
public class BTree {
    public static final int M = 3;
    static class TreeNode{
        public int[] keys;
        public TreeNode[] subs;
        public int usedSize;
        public TreeNode parent;
        public TreeNode(){
            this.keys = new int[M];
            this.subs = new TreeNode[M+1];
        }
     }
     public TreeNode root;
    public boolean insert(int key){

        if(root == null){
            root = new TreeNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        //root 不为空,寻找插入元素是否存在
        Fair<TreeNode, Integer> fair = find(key);
        if(fair.getV()!=-1){
            return false;
        }
        //没找到,进行插入
        TreeNode cur  = fair.getK();
        int index = cur.usedSize-1 ;
        for ( ; index >=0 ;index-- ) {
            if(cur.keys[index] > key){
                cur.keys[index+1] = cur.keys[index];
            }else{
                break;
            }
        }
        cur.keys[index+1] = key;
        cur.usedSize++;
        if(cur.usedSize < M){
            return true;
        }
        //分裂
        split(cur);
        return true;
    }

    private void split(TreeNode cur) {
        TreeNode parent =cur.parent;
        TreeNode newNode  = new TreeNode();
        int mid = cur.usedSize/2 ;
        int i =mid+1;
        int j=0;
        for (; i < cur.usedSize; i++) {
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            if(newNode.subs[j] != null){
                newNode.subs[j].parent = newNode;
            }

            j++;
        }
        newNode.subs[j] = cur.subs[i];
        if(newNode.subs[j] != null){
            newNode.subs[j].parent = newNode;
        }

        newNode.usedSize = j;
        cur.usedSize = cur.usedSize - j - 1;
        if(cur == root){
            root = new TreeNode();
            root.keys[0] = cur.keys[mid];
            root.usedSize = 1;
            root.subs[0] = cur;
            root.subs[1] = newNode;
            newNode.parent= root;
            cur.parent = root;
            return;
        }
        newNode.parent = parent;
        //提中间元素
         int endT  =parent.usedSize-1;
         int midVal = cur.keys[mid];
        for (; endT >= 0 ; endT--) {
            if(parent.keys[endT] > midVal){
                parent.keys[endT+1] = parent.keys[endT];
                parent.subs[endT+2] = parent.subs[endT+1];
            }else{
                break;
            }
        }
        parent.keys[endT+1] =midVal;
        parent.subs[endT+2] = newNode;
        parent.usedSize++;
        if(parent.usedSize < M){
            return ;
        }else{
            split(parent);
        }



    }

    private Fair<TreeNode, Integer> find(int key) {
        TreeNode cur =root;
        TreeNode parent = null;
        while(cur!=null){
            int i= 0;
            while(i < cur.usedSize){
                if(cur.keys[i] < key){
                    i++;
                }else if(cur.keys[i] == key){
                    return new Fair<>(cur,i);
                }else{
                 break;
                }
            }
            parent = cur;
            cur = cur.subs[i];
        }
        return new Fair<>(parent,-1);
    }

    public static void main(String[] args) {

       BTree myBtree =new BTree();
        int[] array = {53, 139, 75, 49, 145, 36,101};
        for (int i = 0; i < array.length; i++) {
            myBtree.insert(array[i]);
        }
        System.out.println("fdsafafa");
        myBtree.inorder(myBtree.root);

    }
    public void inorder (TreeNode root){
        if (root == null)
            return;
        for (int i = 0; i < root.usedSize; ++i) {
            inorder(root.subs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.subs[root.usedSize]);
    }
}
